# leetcode 15 三数之和

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result = set()
        n = len(nums)
        sort_nums = sorted(nums)
        for i in range(n):  # 固定a，从左往右遍历
            left = i + 1    # 左指针 
            rigth = n - 1   # 右指针
            while left < rigth:
                tmp = sort_nums[i] + sort_nums[left] + sort_nums[rigth]
                if tmp > 0:
                    rigth -= 1
                elif tmp < 0:
                    left += 1
                else:
                    a, b ,c = sort_nums[i], sort_nums[left], sort_nums[rigth]
                    result.add(tuple(sorted([a, b, c])))
                    left += 1
        return [list(i) for i in result]
